// Unsigned 64-bit multiplication using the shift-add algorithm
unsigned long __umuldi3(unsigned long a, unsigned long b) {
    unsigned long p = 0; // Product result
    // Iterate until all bits of b are processed
    while (b) {
        if (b & 1)
            p += a;      // If current bit of b is 1, add current a to product
        a <<= 1;         // Shift a left by 1 for next bit position
        b >>= 1;         // Shift b right by 1 to process next bit
    }
    return p;
}

// Signed 64-bit multiplication using unsigned multiplication
long __muldi3(long a, long b) {
    // Convert operands to absolute values (unsigned)
    unsigned long ua = a < 0 ? -a : a;
    unsigned long ub = b < 0 ? -b : b;
    // Perform unsigned multiplication
    unsigned long up = __umuldi3(ua, ub);
    // Determine sign of result and return with correct sign
    return ((a ^ b) < 0) ? -(long)up : (long)up;
}

// Unsigned 64-bit division using restoring division algorithm
unsigned long __udivdi3(unsigned long a, unsigned long b) {
    if (b == 0) return 0; // Division by zero yields zero (could also signal error)
    unsigned long q = 0;  // Quotient result
    // Try to subtract b shifted by i from a, starting from the highest bit
    for (int i = 63; i >= 0; i--) {
        if ((a >> i) >= b) {      // If current shifted a is greater or equal to b
            a -= b << i;          // Subtract b shifted by i from a
            q |= 1UL << i;        // Set the ith bit of quotient to 1
        }
    }
    return q;
}

// Signed 64-bit division using unsigned division
long __divdi3(long a, long b) {
    // Convert operands to absolute values (unsigned)
    unsigned long ua = a < 0 ? -a : a;
    unsigned long ub = b < 0 ? -b : b;
    // Perform unsigned division
    unsigned long ur = __udivdi3(ua, ub);
    // Determine sign of result and return with correct sign
    return ((a ^ b) < 0) ? -(long)ur : (long)ur;
}

// Unsigned 64-bit modulo operation
unsigned long __umoddi3(unsigned long a, unsigned long b) {
    // Compute quotient
    unsigned long q = __udivdi3(a, b);
    // Compute product of quotient and divisor
    unsigned long p = __umuldi3(q, b);
    // Subtract to get remainder (a - (a / b) * b)
    return a - p;
}

// Signed 64-bit modulo operation
long __moddi3(long a, long b) {
    // Convert operands to absolute values (unsigned)
    unsigned long ua = a < 0 ? -a : a;
    unsigned long ub = b < 0 ? -b : b;
    // Compute quotient and product
    unsigned long ur = __udivdi3(ua, ub);
    unsigned long pr = __umuldi3(ur, ub);
    // Compute remainder
    long r = (long)(ua - pr);
    // Adjust sign of remainder to match dividend
    return a < 0 ? -r : r;
}
